# 比较含退格的字符串：  https://leetcode-cn.com/problems/backspace-string-compare/submissions/

# 我感觉我的代码写的好丑，很冗余
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        """
            使用栈很好解决
        """
        stack = []
        i = j = 0
        lenS, lenT = len(s), len(t)
        while i < lenS:
            if s[i] == '#' and stack:
                stack.pop()
            if s[i] != '#':
                stack.append(s[i])
            i += 1
        
        r1 = ''.join(stack)
        stack.clear()
        while j < lenT:
            if t[j]  == '#' and stack:
                stack.pop()
            if t[j] != '#':
                stack.append(t[j])
            j += 1

        r2 = ''.join(stack)

        # print(r1, r2)
        return r1 == r2




class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        """
            双指针从后往前遍历，
            因为 # 可以确定它前面的一个字符被删除， 所以从后往前遍历， 使用指针， 可以每次找到一个确定存在的字符， 
            比较 s, t 中找到的字符是否相等。 一次比较完，如果都相等，那么就相等
        """
        lenS, lenT = len(s), len(t)
        i, j = lenS - 1, lenT - 1
        while i >= 0 or j >= 0:
            skip = 0
            # 1. 先寻找到s一个字符
            while i >= 0 and s[i] == '#':
                skip += 1
                i -= 1
            # 找到第一个字符
            i = max(-1, i - skip)
            c1 = s[i] if i != -1 else ''

            # 2. 先寻找到s一个字符
            skip = 0
            while j >= 0 and t[j] == '#':
                skip += 1
                j -= 1
            # 找到第一个字符
            j = max(-1, j - skip)
            c2 = t[j] if j != -1 else ''
            
            # 这里需要判断一下 例如 t = "c#d#"， 得到的 第一个字符是 # ，这时需要重新循环一次，不能得到 #
            if c1 == '#' or c2 == '#':
                continue
            print(c1, c2)
            # 3. 比较
            if c1 != c2:
                return False
            
            # 4. 指针前移
            i -= 1
            j -= 1
        
        return True


class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        """
            双指针从后往前遍历，
            因为 # 可以确定它前面的一个字符被删除， 所以从后往前遍历， 使用指针， 可以每次找到一个确定存在的字符， 
            比较 s, t 中找到的字符是否相等。 一次比较完，如果都相等，那么就相等
        """
        lenS, lenT = len(s), len(t)
        i, j = lenS - 1, lenT - 1
        while i >= 0 or j >= 0:
            skip = 0
            # 1. 先寻找到s一个字符
            while skip >= 0 and i >= 0:
                if s[i] != "#":
                    skip -= 1
                else:
                    skip += 1
                i -= 1

            # 找到第一个字符
            c1 = s[i+1] if skip < 0 else ''

            # 2. 先寻找到s一个字符
            skip = 0
            while skip >= 0 and j >= 0:
                if t[j] != "#":
                    skip -= 1
                else:
                    skip += 1
                j -= 1

            # 找到第一个字符
            c2 = t[j+1] if skip < 0 else ''
            
            # 3. 比较
            if c1 != c2:
                return False
        
        return True


s = "ab##"
t = "c#d#"

# s = "ab#c"
# t = "ad#c"

a = Solution()
rst = a.backspaceCompare(s, t)
print(rst)

